package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder

/**
654. 最大二叉树
https://leetcode.cn/problems/maximum-binary-tree/description/
https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
 */
class leetcode_654 {

    @Test
    fun test_1() {
        val root = constructMaximumBinaryTree(intArrayOf(3, 2, 1, 6, 0, 5))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(6), arrayListOf(3, 5), arrayListOf(2, 0), arrayListOf(1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_2() {
        val root = constructMaximumBinaryTree(intArrayOf(3, 2, 1))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(3), arrayListOf(2), arrayListOf(1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

//    private fun constructMaximumBinaryTree(nums: IntArray): TreeNode? {
//        // 前序遍历 -  递归
//        // T - N
//        // S - N
//
//
//        // 终止条件
//        if (nums.size == 0) {
//            return null
//        }
//
//        // 中
//        if (nums.size == 1) {
//            val root: TreeNode = TreeNode(nums[0])
//            return root
//        }
//
//        // find the max value ,and index
//        var maxVaue = Int.MIN_VALUE
//        var index = -1
//        for (i in 0..nums.size - 1) {
//            if (nums[i] > maxVaue) {
//                maxVaue = nums[i]
//                index = i
//            }
//        }
//        val root: TreeNode = TreeNode(maxVaue)
//
//        // 左
//        // index 至少不是第0个，才有左孩子
//        if (index >= 1) {
//            val leftNums: IntArray = nums.sliceArray(0 until index) // [0,index)
//            root.left = constructMaximumBinaryTree(leftNums)
//        }
//
//        // 右
//        // index 不能是 end index，才能有右孩子
//        if (index < nums.size - 1) {
//            val rightNums: IntArray = nums.sliceArray(index + 1 until nums.size) // [index + 1, size)
//            root.right = constructMaximumBinaryTree(rightNums)
//        }
//        return root
//    }

    fun constructMaximumBinaryTree(nums: IntArray): TreeNode? {
        /**
         * 题型：二叉树的前序遍历、分割数组
         */
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        if(nums.isEmpty()){
            return null
        }

        // 3 确定单层递归的处理逻辑
        if(nums.size == 1){
            return  TreeNode(nums[0])
        }

        // 确定最大值
        val max: Int = nums.max()
        // 确定index
        val index :Int = nums.indexOf(max)
        val root = TreeNode(max)

        // 根据index 切割左右数组
        val left : IntArray =  nums.sliceArray(0 until index)  // [0, index)
        val right : IntArray = nums.sliceArray(index + 1 until nums.size) // [index + 1, size)
        root.left = constructMaximumBinaryTree(left)
        root.right = constructMaximumBinaryTree(right)
        return root
    }
}